// https://www.lintcode.com/problem/second-minimum-node-in-a-binary-tree/

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the root
     * @return: the second minimum value in the set made of all the nodes' value in the whole tree
     */
    public int findSecondMinimumValue(TreeNode root) {
        // Write your code here
        // 这个结点的值不大于它的两个子结点！！！
        if ((root == null) || ((root.left == null) || (root.right == null))) {
            return -1;
        }
        int lv = -1, rv = -1;
        if (root.left != null) {
            lv = root.left.val;
            if (lv == root.val) {
                lv = findSecondMinimumValue(root.left);
            }
        }
        if (root.right != null) {
            rv = root.right.val;
            if (rv == root.val) {
                rv = findSecondMinimumValue(root.right);
            }
        }
        if ((lv != -1) && (rv != -1)) {
            return Math.min(lv, rv);
        } else if (lv != -1) {
            return lv;
        } else {
            return rv;
        }
    }
}